home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 10705 < prev    next >
Encoding:
Text File  |  1996-08-05  |  3.0 KB  |  107 lines

  1. Path: newsbf02.news.aol.com!not-for-mail
  2. From: mvaccaro1@aol.com (MVaccaro1)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Newbie needs help w/ recursion
  5. Date: 19 Mar 1996 10:56:18 -0500
  6. Organization: America Online, Inc. (1-800-827-6364)
  7. Sender: root@newsbf02.news.aol.com
  8. Message-ID: <4imlf2$osh@newsbf02.news.aol.com>
  9. References: <4ikq6p$io1@impsets.dash.com>
  10. Reply-To: mvaccaro1@aol.com (MVaccaro1)
  11. NNTP-Posting-Host: newsbf02.mail.aol.com
  12.  
  13. >Hi, I am new and am about to pull my hair out over the supposedly simple
  14. >recursion problem I have. The function is to take a number and raise it
  15. >to a neg or pos power and return the value to main().  I need to take
  16. >the following and make it a recursive function...
  17.  
  18. >double power (double a, float b)
  19. >  {
  20. >  double power = 1;
  21. >  int i;
  22.    .
  23.    .
  24.    .
  25.  
  26. Dianna,
  27.  
  28. Recursive programming requires thinking along the lines of step wise tasks
  29. until
  30. some point is reached where the task is done.  To use your power function,
  31. examine the problem this way:
  32.  
  33.   x raised to the power of 0 is 1 /* this is the end of the task chain */
  34.   x raised to the power of 1 is x times x raised to the power of 0
  35.   x raised to the power of 2 is x times x raised to the power of 1
  36.   .
  37.   .
  38.   .
  39.   x raised to the power of n is x times x raised to the power of n-1.
  40.  
  41. thus, in psuedo code, a recursive function of this nature would look like
  42. this:
  43.  
  44.   function ( x, n )
  45.     if n is greater than 0
  46.       return x * function( x, n - 1 );
  47.     else
  48.       return 1
  49.   endfunction
  50.  
  51. or in C
  52.  
  53.    double power( double x, int n )
  54.       {
  55.       if ( n > 0 )
  56.          return x * power( x, n- 1 );
  57.       else
  58.          return 1;
  59.       }
  60.  
  61. Let x = 2 and n = 2 when the function is first called.  The first time
  62. through
  63. the statement "return x * power( x, n - 1);" will be executed which means
  64. that
  65. the function power( x, n - 1 ) must be evaluated first before the return
  66. can be
  67. executed.  Thus we enter power a second time (recursively) with x = 2 and
  68. n = 1.
  69. This second time with n = 1, the statement "return x * power( x, n - 1 );"
  70. is
  71. executed with the function power being entered a third time. In the third
  72. iteration
  73. of power, n is now equal to 0 causing the third iteration to return 1.  1
  74. is
  75. returned to the second iteration which was in the process of a return
  76. statement.
  77. The second iteration returns 2 ( x = 2 and power( x, n-1 ) = 1) so 2 * 1 =
  78. 2).
  79. The second iteration returns to the first iteration which was also in the
  80. process
  81. of executing a return. Now the first iteration's return is 2 * 2, (x=2 and
  82. power(x , n - 1) = 2 this time around).  The function power finally
  83. returns a
  84. value of 4.
  85.  
  86. Handling negative numbers requires additional code as follows:
  87.  
  88.    double power( double x, int n )
  89.       {
  90.       if ( n > 0 )
  91.          return x * power( x, n- 1 );
  92.       else if ( n < 0 )
  93.          return ( 1/x ) * power( x, n + 1 );
  94.       else
  95.          return 1;
  96.       }
  97.  
  98. Thus when n is -2, 0.25 is returned.  Handling fractional exponentiation
  99. is beyound
  100. the scope of my own laziness but I think you get the idea.
  101.  
  102. I hope this helps.
  103.  
  104. Mike:->
  105.  
  106. Design? What design! - I've too much coding to do...
  107.